Réseaux d'interaction protéine/protéine

Un article de Wikipédia, l'encyclopédie libre.

Les réseaux d'interaction protéine-protéine (IPP), de la génération du réseau[Quoi ?] à sa visualisation, de l'extraction des métriques[Quoi ?] à la compréhension de la topologie[Quoi ?] ou à la détection des communautés[Quoi ?], trouve son importance entre autres dans la compréhension des pathologies, la fonction des protéines.

Les réseaux en Biologie[modifier | modifier le code]

Les systèmes biologiques sont extrêmement complexes. Les processus biologiques à l’intérieur des cellules caractérisés entre autres par les interactions entre les molécules qui s’y trouvent  ne peuvent être compris en étudiant molécule par molécule car elles fonctionnent souvent de manière différente suivant le mécanisme dans lequel elles sont impliquées.. Aussi, de nouvelles caractéristiques biologiques absentes dans des composants isolés apparaissent selon le type d’interaction entre ces composants. Ce qui explique l'intérêt pour les réseaux d’interactions, dont l’un des principaux défis consiste à comprendre et à analyser leurs structures et leurs dynamiques.  Les techniques de collecte de données à haut débit, le développement des bases de données moléculaires (protéines, gènes, métabolites…) facilitent l’étude et la génération de plusieurs types de réseaux biologiques[1].

Les réseaux biologiques sont généralement classés selon la nature des molécules impliquées.

Réseaux de régulation des gènes[modifier | modifier le code]

La transcription d’un gène en ARNm est régulée par les facteurs de transcriptions (FT), protéines avec au moins un domaine de liaison à l’ADN. En se liant à ces domaines, les FT  activent ou inhibent la production d’une autre protéine. Dans les organismes unicellulaires, les réseaux de régulation des gènes sont essentiels pour réguler l’activité cellulaire afin de survivre aux conditions environnementales externes. Dans les organismes multicellulaires, ces réseaux servent à l’activité cellulaire en fonction de la fonction particulière que la cellule doit remplir. Trois types de modèles ont été proposés pour les réseaux de régulation des gènes[1].

  • Modèle logique ou booléen: description des réseaux de régulation d’un point de vue qualitatif pour comprendre si un gène est activé ou non à un moment donné de la vie du système
  • Modèle continu: description des réseaux d’un point de vue quantitatif (concentration des molécules…)
  • Modèles à molécule unique: sur le bruit qui affectent la fonctionnalité des réseaux

Réseaux de signalisation[modifier | modifier le code]

Les cellules ont la capacité de recevoir et de traiter des signaux qui proviennent de l'extérieur afin de répondre aux changements dans leur environnement immédiat. Cette communication est rendue possible par des réseaux de signalisation et de transduction cellulaires. On en distingue 5 classes: intracrine, autocrine, juxtacrine, paracrine, endocrine selon l’origine et la cible des signaux, et 3 classes selon la molécule de signalisation (hormones, neurotransmetteurs, cytokines)[1].

Réseaux métaboliques[modifier | modifier le code]

Ils représentent l’ensemble des réactions métaboliques de la cellule. Un réseau complet de plusieurs organismes, des bactéries à l’homme, peuvent être reconstruits grâce au séquençage et d’ailleurs plusieurs de ces réseaux sont disponibles dans plusieurs bases de données telles que KEGG. Il existe des réseaux métaboliques simplifiés (réaction, enzyme, substance), des réseaux de métabolites (uniquement de substances) et métabolites simplifiés (substances principales) ainsi que des réseaux d’enzymes[1]

Réseaux de co-expression des gènes[modifier | modifier le code]

Ils permettent d’identifier les gènes qui sont contrôlés par la même régulation transcriptionnelle qui sont fonctionnellement liés, ou dont les gènes sont impliqués dans un processus biologique commun. Ces réseaux ne fournissent cependant aucune information sur les relations de causalité entre les gènes (activation ou inhibition). Ils sont constitués en 2 étapes principales: calcul d’une mesure de co-expression (matrice d’expression) et sélection d’un seuil de significativité (coefficient de corrélation de Pearson, distance euclidienne, corrélation de Spearman...)[1].

Réseaux IPP[modifier | modifier le code]

Les protéines sont les principaux agents de la fonction biologique. Elles contrôlent les mécanismes moléculaires et cellulaires et par conséquent, déterminent les états sains et malades des organismes. Toutefois, elles ne sont pas fonctionnelles sous forme isolée, mais elles interagissent entre elles et avec d'autres molécules (par exemple, l'ADN et l'ARN) pour remplir leurs fonctions. Ainsi, l'étude des interactions des protéines est cruciale pour comprendre leur rôle à l'intérieur de la cellule. Comme ce type d'interactions peut être de plusieurs types, le terme d'interaction protéine-protéine fait référence à une variété d'événements se produisant à l'intérieur de la cellule[1].

En biologie moléculaire, un interactome est l'ensemble des interactions moléculaires dans une cellule particulière. Dans le cas des protéines, également connues sous le nom d’interactions protéines-protéines IPP. Les interactions basées sur les IPP doivent être associées au protéome de l'espèce correspondante afin de fournir une vue globale ("omique") de toutes les interactions moléculaires possibles qu'une protéine peut présenter[2].

Un réseau d'interaction protéine-protéine stocke les informations sur l'interactome protéine-protéine d'un organisme donné, c'est-à-dire l'ensemble de ses interactions protéine-protéine. Il a été suggéré que la taille des interactomes protéine-protéine augmente proportionnellement à la complexité biologique des organismes, aucun interactome protéine-protéine n'a été complètement identifié et, par conséquent, cette corrélation ne reste qu'une conjecture. En outre, les réseaux d'interaction protéine-protéine disponibles sont sujets à des erreurs, car les méthodes expérimentales utilisées pour découvrir les interactions peuvent inclure des faux positifs ou ne pas révéler certaines interactions existantes. Malgré cela, les réseaux d’interaction protéine-protéines sont particulièrement important dans de nombreux contextes:

  • l'analyse de ces réseaux facilite la compréhension des mécanismes qui déclenchent le début et la progression des maladies
  • les réseaux d'interaction protéine-protéine ont été utilisés pour découvrir de nouvelles fonctions des protéines[3] et pour identifier des modules fonctionnels et des modèles d'interaction conservés[4].
  • certains travaux sur la structure des réseaux d'interaction protéine-protéine de plusieurs espèces ont permis de découvrir que, indépendamment de l'espèce, les réseaux d'interaction protéine-protéine sont sans échelle. Cela signifie que certaines protéines "hub" ont un rôle central participant à la majorité des interactions alors que la plupart des protéines, qui ne sont pas des "hubs", ne participent qu'à une petite fraction des interactions

Les sources de données[modifier | modifier le code]

Les réseaux IPP sont un des types de réseaux biologiques, et se rejoignent sur les ressources utilisées pour leur réalisation. Ceci est la première étape pour construire un réseau. Il existe différentes sources de données IPP  qui peuvent être utilisées pour ce faire et il est important de connaître leurs avantages et leurs inconvénients.

Vous  pouvez obtenir des données IPP de[5]:

   Vos propres travaux expérimentaux, où vous pouvez choisir la manière dont les données sont représentées et stockées

   Une base de données IPP primaire. Ces bases de données extraient les IPP à partir des preuves expérimentales rapportées dans la littérature en utilisant un processus de traitement manuel. Elles sont les principaux fournisseurs de données sur les IPP et peuvent représenter beaucoup de détails sur les interactions, selon la base de données.

   Une base de métadonnées ou une base de données prédictive. Ces ressources rassemblent les informations fournies par différentes bases de données primaires et fournissent une représentation unifiée des données à l'utilisateur. Les bases de données prédictives vont plus loin et utilisent les ensembles de données produites expérimentalement pour prédire par calcul les interactions dans les zones inexplorées de l'interactome. Les bases de données prédictives offrent un moyen d'élargir ou d'affiner l'espace des interactions dérivées expérimentalement, mais les ensembles de données produits sont plus bruyants que ceux provenant d'autres sources

Base de données pour réseaux IPP

Il existe plusieurs base de données pour construire des réseaux IPP. On peut citer

  • BioCyc , KEGG, Reactome, DIP, STRING.

Plus de détails sur Protein–Protein Interaction Databases[6]

Figure 1 - Les bases de données IPP et leurs sources[6]. Copyright 2019 Elsevier Inc.

Topologie et métriques des réseaux[modifier | modifier le code]

La théorie des réseaux complexes se base sur le principe que toutes les interactions, qu’elles soient physiques ou fonctionnelles, peuvent être conceptualisées sous la forme abstraite d’un réseau, composé de nœuds et de liens. Chaque nœud représente un élément du réseau, et chaque lien une interaction.

Un réseau peut être orienté ou non orienté. Dans le cas d’un réseau orienté, l’interaction entre deux nœuds est dirigée.

Cette approche a démontré qu’il existe des lois universelles communes à la plupart des réseaux complexes[7],[8]. Ainsi, les réseaux biologiques partagent les mêmes caractéristiques que d’autres systèmes complexes tels que les puces informatiques ou Internet.

Cette notion permet de caractériser dans l’espace, la géométrie des réseaux IPP. De là, plusieurs méthodes de mesures peuvent être calculées.

Mesures quantifiables[modifier | modifier le code]

Il existe plusieurs mesures quantifiables pour caractériser un réseau et faciliter la conceptualisation de systèmes complexes tels que les interactions entre molécules (ex : réaction enzyme/substrat) :

Le degrés k[modifier | modifier le code]

Le degrés k d’un nœud indique combien ce nœud a de liens avec d’autres nœuds.

La distribution des degrés P (k)[modifier | modifier le code]

P(k) donne la probabilité qu'un nœud ait exactement k liens. P (k) est obtenu en divisant le nombre nœuds avec k liens et en par le nombre total de nœuds.

Le degré exposant γ[modifier | modifier le code]

Si la distribution des degrés d’un réseau suit une loi de Poisson, alors P(k) est proportionnel à k-γ. Plus γ est petit, plus les hubs ont un rôle important dans le réseau. Pour une valeur de γ supérieure à 3, les hubs ne sont plus significatifs.

Chemin le plus court et longueur moyenne du chemin[modifier | modifier le code]

La distance dans les réseaux est mesurée avec la longueur du chemin, qui nous indique combien de liaisons nous devons traverser pour nous déplacer. Il existe de nombreux chemins possibles entre deux nœuds. Le chemin le plus court est celui avec le plus petit nombre de liens entre les nœuds sélectionnés. On peut calculer le plus court chemin moyen entre toutes les paires de nœuds pour mesurer la navigabilité globale d’un réseau.

La Betweenness B[modifier | modifier le code]

C’est une mesure permettant d’analyser la centralité des nœuds d’un réseau et est basée sur les plus courts chemins. Celle-ci indique le nombre de plus courts chemins passant par le nœud considéré. Ainsi, il est possible de déterminer si le nœud contrôle ou non le flux d’informations d’un réseau (plus la fréquence de passage à ce nœud est élevée, plus il contrôle le réseau).

Le Coefficient de clustering[modifier | modifier le code]

Si les nœuds A et B et B et C sont respectivement connectés, alors il est très probable que A et C le soient aussi[9]. Ce phénomène peut être quantifié à l'aide du coefficient de clustering CI :

Avec nI, le nombre de liens reliant les k voisins du nœud I entre eux. En d’autres termes, CI donne le nombre de “triangles” qui passent par le nœud I. Le coefficient de clustering moyen d’un réseau caractérise donc la tendance générale des nœuds à former des clusters ou groupes. Une mesure importante de la structure du réseau est la fonction C (k), qui est définie comme le coefficient de clustering moyen de tous les nœuds avec k liaisons. Un C (k) proportionnel à k - 1, un réseau de type hiérarchique[10],[11].

Le degré moyen, la longueur moyenne du chemin, et le coefficient de clustering moyen dépendent du nombre de nœuds et de liens du réseau. En revanche, les fonctions P (k) et C (k) sont indépendantes de la taille du réseau ce qui permet de les utiliser pour classer les réseaux.

Les différents réseaux[modifier | modifier le code]

Depuis des décennies, la théorie des graphes permet, grâce aux mathématiques fondamentales, de modéliser des systèmes complexes en objets géométriques réguliers ou en réseaux aléatoires. C’est en 1960 que Paul Erdös et Alfred Rényi initient l’étude des propriétés mathématiques des réseaux[12], permettant ainsi leur classification (cf. figure 2):

Les réseaux aléatoires[modifier | modifier le code]

Figure 2 - Théorie des graphes - Topologie des réseaux[13]. Copyright © 2004, Nature Publishing Group.

Caractérisés par un nombre fixe de nœuds connectés aléatoirement. La distribution des degrés des nœuds suit une loi de Poisson . La plupart des nœuds ont donc le même nombre de liens, ce qui permet d’établir un nœud typique du réseau, mais ce qui n’explique pas la topologie des réseaux réels.

Les réseaux scale-free (sans échelle)[modifier | modifier le code]

Ces derniers suivent une loi de Puissance[14]. Quelques nœuds centralisent la majorité des liens et constituent un hub. Il n’y a donc pas de nœud consensus qui permettrait de caractériser tous les nœuds du réseau. Quel que soit le règne ou l’organisme, les réseaux cellulaires sont de type scale free dirigés[14], où les nœuds sont des métabolites et les liens représentent les réactions biochimiques.

Les réseaux hiérarchiques[modifier | modifier le code]

Pour tenir compte de la modularité, du clustering local et de la topologie sans échelle dans de nombreux systèmes réels, il faut supposer que les clusters se combinent de manière itérative, générant un réseau de type hiérarchique[1],[11]. La particularité de ce type de réseau est que le coefficient de clustering C(k) est inversement proportionnel à k-1.

Caractéristiques des réseaux IPP[modifier | modifier le code]

Une propriété à retenir des réseaux IPP c’est qu’ils ne sont pas fixes. En effet, il peut y avoir des gains ou pertes de nœuds avec les liens dédiés qui sont provoqués par des évènements génétiques. Pour illustrer cela des mutations, insertions ou même des duplications peuvent induire le rajout de nœuds avec les liens impliqués ou alors les pertes de gènes amènent à la perte des nœuds et liens. D’autres événements peuvent modifier une partie de l’expression et à la régulation d’un gène et ainsi contrôler une partie de gain et de pertes d’interactions[15]. Il a été supposé que la taille du génome pouvait influencer le nombre d’interactions au sein d’un réseau.

Par la suite, il est important de noter qu’un réseau IPP n’est pas le même dans le temps et dans l’espace en raison de la répartition des protéines et que ce dernier change constamment. Les réseaux IPP sont très dynamiques.

Topologie de réseau[modifier | modifier le code]

Figure 3 - Réseau d’interaction protéine / protéine de S.Cerevisiae, un réseau à topologie mixte. Copyright © 2004, Nature Publishing Group[13].

Plusieurs études[16],[17] ont démontré que les réseaux d’interactions protéines/protéines sont de type scale-free (exemple: figure 3 - réseau IPP de Saccharomyces Cerevisiae). C’est aussi le cas des réseaux de régulations génétiques. Cependant, tous les réseaux intra-cellulaires ne sont pas de type scale-free. Par exemple, les réseaux de régulation de la transcription de S.Cerevisiae et Escherichia coli offrent un exemple de caractéristiques mixtes.

L’étude des réseaux métaboliques a montré qu’une perturbation locale pouvait impacter rapidement tout le réseau du fait de l’interconnexion quasi totale des métabolites.

L’ensemble des réseaux biologiques de type scale-free suivent un principe dissortatif, c’est-à-dire que les hubs vont avoir tendance à se connecter à des protéines intermédiaires isolées, plutôt qu’à se connecter directement entre eux.

Dans le cadre des réseaux d’interaction protéines/protéines, des comparaisons inter-génomiques ont prouvé que les protéines les plus anciennes sont impliquées dans plus de liens que leurs homologues plus jeunes[18],[19]. Il y a donc un phénomène évolutif des réseaux d’interaction complexes.

Visualisation des réseaux IPP[modifier | modifier le code]

Les réseaux IPP d’une cellule entière sont très rares dans les publications scientifiques à cause de leur complexité visuelle et de gestion.  Néanmoins, au fil des années, les scientifiques étudient ces réseaux de différentes manières. Pour la visualisation des réseaux, le logiciel Cytoscape est très largement utilisé pour tous types de réseaux dont ceux des interactions Protéine-Protéine.

Cytoscape est un logiciel open source bio-informatique qui permet la visualisation des réseaux d'interactions moléculaires et l'intégration des profils de gènes ou d'autres données d'état.

Détection des communautés[modifier | modifier le code]

Notion de modularité[modifier | modifier le code]

Les fonctionnalités cellulaires s’organisent en module[20]. Un module est constitué par un groupe de molécules liées physiquement ou fonctionnellement, et qui agissent ensemble. On peut citer en exemple les complexes inter-protéiques invariants, les complexes ARN/protéine, ou encore les groupes de protéines qui sont liés par une action temporelle commune (ex : régulateurs du cycle cellulaire).

La plupart des molécules cellulaires sont impliquées dans un complexe modulaire. L’utilisation du coefficient de clustering est utile pour étudier la modularité des réseaux :  plus le coefficient est élevé, plus le réseau comporte de modules. C’est le cas des réseaux cellulaires, en particulier les inter-protéiques ainsi que les réseaux d’interaction de domaines protéiques.

Les clusters, les hubs, et les modules coexistent au sein du réseau. Les modules ne sont donc pas indépendants, et se combinent en réseau hiérarchique[21],[22]. L’identification des modules impliqués dans les fonctionnalités cellulaires est une des clefs du développement des réseaux biologiques à venir. La plupart des méthodes de clustering permettent d’identifier les modules d’un réseau, si ces derniers sont clairement séparés. D’autres méthodes, qui combinent critères topologiques et données génomiques permettent de traiter les cas plus complexes[23],[24]

Sous-graphs, motifs et clusters de motifs[modifier | modifier le code]

Alors que les caractéristiques des réseaux hiérarchiques et scale free mettent l'accent sur les principes d'organisation qui déterminent la structure à grande échelle du réseau, une approche alternative commence par le bas et recherche des modèles d'interactions qui caractérisent des réseaux spécifiques.

  • Les sous-graphs: un sous-graph représente un sous-ensemble de nœuds qui sont connectés les uns aux autres selon un schéma spécifique (cf. figure 4).  Le nombre de sous-graphs distincts croît de façon exponentielle avec le nombre de nœuds.
  • Les motifs: les sous-graphs n’ont pas tous la même fréquence d’apparition. Un sous-graph qui apparaît plus fréquemment que sa fréquence aléatoire obtenue par randomisation du réseau, constitue un motif du réseau.
  • Les clusters de motifs: les sous-graph et motifs d’un réseau ne sont pas indépendants. Dans l’exemple de la figure 3D (réseau de régulation de la transcription d’E.coli)[25], les motifs se regroupent en cluster. Un seul motif en bas à gauche est isolé.
Figure 4 - Théorie des graphes - Clusters et motifs - Copyright © 2004, Nature Publishing Group[13].

Les outils de détection des communautés[modifier | modifier le code]

MCode[modifier | modifier le code]

MCODE[26] est l'un des premiers algorithmes explicitement conçus pour regrouper les réseaux IPP. MCODE est organisé en quatre phases. Dans la première phase, chaque nœud v se voit attribuer un poids qui est le produit du coefficient de regroupement des noyaux de v et la valeur maximale k pour laquelle il existe un noyau k dans N G (v). Les nœuds sont classés par valeurs décroissantes de leur poids et utilisés comme semences dans cet ordre pour la phase suivante. Dans la deuxième phase, en partant du nœud inutilisé le plus élevé en rang, MCODE ajoute itérativement voisins de la grappe en cours de construction, à condition que leur poids soit supérieur à une fraction fixe du poids de la graine. Les nœuds ajoutés sont marqués comme étant utilisés. Dans la troisième phase, les groupes qui ne comportent pas de noyau double sont rejetés et il est possible d'augmenter le se groupent avec les nœuds voisins au-dessus d'une certaine fraction fixe du poids de la graine. Ces nœuds supplémentaires ne sont pas marqués comme étant utilisés, Ils peuvent donc être partagés entre plusieurs communautés. L'étape finale consiste à calculer le plus grand noyau connecté de chaque candidat.

C-finder[modifier | modifier le code]

C-Finder[27] est un programme rapide qui met en œuvre la méthode CPM (Clique Percolation Method) pour le regroupement des graphiques[28]. L'algorithme fonctionne en deux phases principales. La première phase consiste à trouver tous les k-cliques dans le réseau d'entrée, puis CFinder associe deux k-cliques si elles partagent une (k 1)-clique commune. Les clusters produits par CFinder sont les classes d'équivalence de cette relation d'association. Notez que les groupes distincts produits peuvent partager des nœuds, et l'intersection de deux groupes peut contenir des (k 2)-cliques mais jamais une (k 1)-clique. CFinder a été l'un des premiers algorithmes de clustering qui a pu contrôler étroitement la structure de chevauchement de la famille de clusters qu'il produit. Le paramètre k est critique et pour les applications biologiques, une valeur de l'ordre de k1⁄4 4,5,6 est suggérée dans la publication originale.

CMC[modifier | modifier le code]

L'algorithme CMC (Clustering Based on Maximal Cliques)[29] fonctionne avec des graphes pondérés par les bords. CMC commence par lister toutes les cliques maximales dans un graphe G en utilisant l'algorithme de Tomita et al. (2006)[30], une variante rapide de la méthode de Bron-Kerbosch[31]. Dans la phase suivante, chaque clique maximale reçoit un score qui correspond à son poids moyen à la limite, et ces grappes sont classées par ordre décroissant de valeur de score. Dans la phase suivante, pour chaque groupe C i, les algorithmes considèrent tour à tour les groupes C j de valeur inférieure et décide de fusionner C i et C j (ou de supprimer C j ) sur la base de l'importance relative de leur chevauchement et d'une pondération inter-fonction de score de cluster.

Il existe aussi d’autres algorithmes tels que : Coach, SPICI and ClosterOne, ProBank et Core & Peel (voir plus Pellegrini & all. Community Detection in Biological Networks[32].

Alignement des réseaux IPP[modifier | modifier le code]

L'objectif ultime de l'alignement des réseaux est de transférer la connaissance de la fonction des protéines d'une espèce à l'autre en alignant deux réseaux d'IPP et ainsi de compléter la similarité de séquence par des informations topologiques afin d'identifier les orthologues aussi précisément que possible. En supposant que nous avons k graphes et que chaque graphe a n nœuds, chaque tuple contient k nœuds, un de chaque graphe. Idéalement, nous devrions avoir n tuplets dans l'alignement global avec la stipulation qu'une valeur métrique d'alignement est optimisée.

Méthodes d'évaluation[modifier | modifier le code]

De nos jours, aucune solution optimale est inconnue pour l'alignement de réseaux IPP. De ce fait, il devrait y avoir une méthode pour évaluer les divers résultats extraits à l'aide de différents aligneurs. Deux gros ensembles de mesures d'évaluation sont ainsi utilisés pour évaluer la qualité des alignements.

La première série évalue la qualité des caractéristiques topologiques de l'alignement. Le second ensemble mesure l'essence de l'alignement en tenant compte de l'ajustement biologique.

Évaluation topologique[modifier | modifier le code]

Correction des bords (EC : edge correctness)[modifier | modifier le code]

La correction des bords est la mesure la plus populaire utilisée pour mesurer la qualité topologique des alignements de réseaux. La EC calcule le pourcentage d'arêtes du premier réseau qui sont cartographiées, aux arêtes du second réseau[33].

Structure conservée induite (ICS : induced conserved structure)[modifier | modifier le code]

Pour pallier les faiblesses de la EC, le score ICS a été introduit pour contourner les nœuds d'alignement du premier réseau vers les régions denses du second réseau où les possibilités d'alignement de différentes manières sont élevées. Le score ICS pénalise un tel alignement alors que la EC ne le fait pas[34].

Score de sous-structure symétrique (S3 : symmetric substructure score)[modifier | modifier le code]

Alors que le SCI s'attaque à une faiblesse de la EC en pénalisant les alignements clairsemés à denses, il ne punit pas de la même façon les alignements denses à clairsemés. Pour améliorer la situation, le score de sous-structure symétrique pénalise de la même manière les alignements clairsemés à denses et denses à clairsemés. Dans les alignements méta-heuristiques, il a été démontré que cette mesure est un prédicteur plus fiable d'un alignement correct que la EC et l'ICS[35].

Plus grande sous-composante commune connectée (LCCS : Largest common connected sub-component)[modifier | modifier le code]

La taille de la plus grande sous-composante commune connectée considère que de grandes sous-graphiques connectées sont souhaitables. Des scores EC, ICS ou S3 élevés ne reflètent pas nécessairement le fait que les nœuds alignés forment une sous-structure connectée[33].

Correction des nœuds (NC : Node correctness) et des interactions (IC : Interaction Correctness)[modifier | modifier le code]

Deux autres mesures d'évaluation exigent que le véritable alignement de deux réseaux IPP soit connu afin d'estimer la qualité de l'alignement extrait. Si l'alignement est réel, alors la correction des nœuds (NC) est le pourcentage de nœuds alignés correctement. De même, la correction des interactions (IC) est définie comme le pourcentage d'interactions (c'est-à-dire les bords) correctement cartographiées[36],[33].

L'évaluation des alignements sur la base de la qualité topologique n'est pas toujours suffisante. L'évaluation des alignements basée uniquement sur des mesures topologiques ne signifie pas que la qualité de l'alignement est certainement bonne. L'alignement doit être évalué de manière à confirmer que les protéines alignées correspondent à des modules fonctionnels conservés au cours de l'évolution.

Évaluation biologique[modifier | modifier le code]

Les mesures biologiques évaluent la qualité de l'alignement par rapport aux similitudes fonctionnelles entre les deux nœuds (protéines) qui sont cartographiés l'un par rapport à l'autre.

Ontologie des gènes (GO : gene ontology)[modifier | modifier le code]

Les alignements utilisent généralement les annotations de l’ontologie génétique afin de juger de la similarité fonctionnelle des nœuds alignés. Les annotations de l'ontologie des gènes pour chaque protéine sont collectées et comparées pour voir si elles représentent des fonctions similaires[34],[37].

La façon naïve d'évaluer le chevauchement des termes GO consiste à rapporter directement le pourcentage de paires de protéines alignées dans l'alignement qui partagent plus de k annotations GO[38],[39].

La similarité sémantique de Resnik[modifier | modifier le code]

La mesure de similarité sémantique de Resnik, est l'une des mesures de similarité ontologique les plus courantes qui prend en compte la structure hiérarchique, utilisée afin de concevoir une mesure biologique pour évaluer les alignements de réseaux biologiques. La structure hiérarchique de l'ontologie GO a été prise en compte pour calculer la similarité[34],[40].

Cohérence de l'ontologie des gènes (GOC: gene ontology consistency)[modifier | modifier le code]

GOC utilise les annotations GO pour évaluer la qualité de l’alignement[41].

Cohérence normalisée de l'ontologie des gènes (NGOC: normalized gene ontology consistency)[modifier | modifier le code]

Le NGOC améliore l'évaluation de l'alignement du réseau IPP pour l'ajustement biologique en prenant en compte le nombre total de protéines alignées[42].

Comme toutes les mesures d'évaluation biologique additionnant le score des nœuds alignés, un alignement peut être meilleur en cartographiant simplement plus de protéines que dans d'autres alignements.

Aligner les réseaux IPP[modifier | modifier le code]

L'objectif est de découvrir de grands sous-réseaux partagés entre les espèces et de dériver des relations phylogénétiques entre les espèces en examinant l'étendue du chevauchement présenté par les différents réseaux IPP. L'analyse comparative des réseaux de IPP entre les espèces permet d'identifier les sous-réseaux évolutifs conservés. Elle est souvent considérée comme un problème d'alignement des graphes où les protéines de différentes espèces sont superposées les unes aux autres sur la base des preuves accumulées de la grande similarité des séquences protéiques ainsi que de la grande similarité topologique[43].

Définition[modifier | modifier le code]

Étant donné k réseaux IPP distincts  de k espèces différentes, le problème d'alignement des IPP est de trouver un sous-réseau conservé A, dans chacun des k graphes. Le graphe d'alignement A est un sous-graphe composé de nœuds représentant k protéines similaires (une par espèce), et d'arêtes représentant les interactions conservées entre les espèces. Chaque alignement Ai peut être représenté comme :

Le problème d'alignement recherche un ensemble optimal  alignements en maximisant la couverture des sommets de tous les réseaux participants.

Alignements par paires[modifier | modifier le code]

Un alignement de réseau IPP par paire est un alignement limité à deux espèces seulement (k = 2). Étant donné deux réseaux, on trouve un alignement optimal des nœuds entre les deux. Le principal objectif de l'alignement de deux réseaux d'IPP de deux espèces est de trouver des protéines conservées chez les deux espèces. Avec deux ou plusieurs réseaux d'IPP, on peut effectuer deux types d'alignement : l'alignement global ou l'alignement local.

Figure 5 - Comparaison de l'alignement des réseaux locaux et globaux. Les lignes en pointillés reliant les nœuds de différents réseaux (de différentes couleurs) représentent un alignement de la paire de nœuds. (a) Alignement du réseau local (alignement un à plusieurs) ; (b) Alignement du réseau global (alignement un à un).[44]

Dans l'alignement global, chaque nœud d'un réseau est aligné sur un seul nœud de l'autre réseau, ce qui produit une seule correspondance globale de deux ou plusieurs réseaux. Dans l'alignement global des réseaux, chaque nœud du plus petit réseau est aligné de manière unique sur un seul nœud du plus grand réseau qui correspondra le mieux. Un tel alignement permet de détecter un sous-réseau maximal, ce qui est utile pour la prédiction de l'orthologie fonctionnelle[45],[46].

En revanche, l'alignement local tente de trouver le meilleur alignement des sous-réseaux d'un réseau avec les sous-réseaux d'un autre réseau, sans se soucier de la façon dont les autres nœuds s'alignent. Les méthodes d'alignement local peuvent produire des alignements de nœuds d’un à plusieurs, où un nœud d'un réseau peut être aligné sur plusieurs nœuds de l'autre réseau. Dans l'alignement local, les petites régions de similarité sont appariées indépendamment, et plusieurs de ces régions peuvent se chevaucher de manière conflictuelle. Sur le plan informatique, l'alignement local est moins coûteux que l'alignement global, car ce dernier vise à trouver une seule grande correspondance cohérente[44].

Alignements multiples[modifier | modifier le code]

Figure 6 - Exemple d'alignements multiples de réseaux pour N réseaux IPP différents. Les nœuds ont des formes variées pour représenter la diversité des molécules de protéines. Les bords des nœuds inter-réseaux indiquent les alignements possibles par rapport à certains paramètres d'alignement tels que l'ontologie ou la similarité topologique.[46]

Si nous avons k réseaux IPP (avec k > 2), et que nous sommes chargés de trouver un alignement de tous les réseaux, le problème devient plus difficile. L'alignement de plusieurs réseaux IPP peut permettre de mieux comprendre les fonctions et les interactions des protéines, ce qui conduira à une meilleure compréhension de l'évolution des espèces. Même si les alignements de réseaux multiples ont été conçus et mis en œuvre pour traiter plus de deux réseaux d'entrée, ils peuvent toujours être utilisés comme des alignements par paires lorsque le nombre de réseaux IPP n'est que de deux[44].


Tableau 1- Comparaison de différentes techniques d’alignements IPP[44].
Alignement Technique Année Alignement par pair Alignement multiple Approche topologique Approche fonctionnelle
Alignement local Graemlin 2006
Graemlin 2.0 2009
NetworkBLAST 2008
NetAligner 2012
Alignement global IsoRank 2008
IsoRankN 2009
GRAAL 2009
GHOST 2012
Optnetalign 2015
PROPER 2016

Références[modifier | modifier le code]

  1. a b c d e f et g (en) Valeria Fionda, « Networks in Biology », dans Encyclopedia of Bioinformatics and Computational Biology, Elsevier, (ISBN 978-0-12-811432-2, DOI 10.1016/b978-0-12-809633-8.20420-2., lire en ligne), p. 915–921
  2. (en) Diego Alonso-López, Miguel A. Gutiérrez, Katia P. Lopes et Carlos Prieto, « APID interactomes: providing proteome-based interactomes with controlled quality for multiple species and derived networks », Nucleic Acids Research, vol. 44, no W1,‎ , W529–W535 (ISSN 0305-1048, PMID 27131791, PMCID PMC4987915, DOI 10.1093/nar/gkw363, lire en ligne, consulté le )
  3. (en) Valeria Fionda, Luigi Palopoli, Simona Panni et Simona E. Rombo, « A technique to search for functional similarities in protein-protein interaction networks », International Journal of Data Mining and Bioinformatics, vol. 3, no 4,‎ , p. 431 (ISSN 1748-5673 et 1748-5681, DOI 10.1504/IJDMB.2009.029205, lire en ligne, consulté le )
  4. (en) Valeria Fionda, « Biological network analysis and comparison: mining new biological knowledge », Open Computer Science, vol. 1, no 2,‎ , p. 185–193 (ISSN 2299-1093, DOI 10.2478/s13537-011-0013-1, lire en ligne, consulté le )
  5. (en) EMBL-EBI, « Sources of PPI data | Network analysis of protein interaction data » (consulté le )
  6. a et b Max Kotlyar, Chiara Pastrello, Andrea E.M. Rossos et Igor Jurisica, « Protein–Protein Interaction Databases », dans Encyclopedia of Bioinformatics and Computational Biology, Elsevier, (ISBN 978-0-12-811432-2, lire en ligne), p. 988–996
  7. Réka Albert et Albert-László Barabási, « Statistical mechanics of complex networks », Reviews of Modern Physics, vol. 74, no 1,‎ , p. 47–97 (ISSN 0034-6861 et 1539-0756, DOI 10.1103/revmodphys.74.47, lire en ligne, consulté le )
  8. Albert-László Barabási, « Evolution of Networks: From Biological Nets to the Internet and WWW Evolution of Networks: From Biological Nets to the Internet and WWW , S. N. Dorogovtsev and J. F. F. Mendes Oxford U. Press, New York, 2003. $95.00 (264 pp.). (ISBN 0-19-851590-1) », Physics Today, vol. 57, no 10,‎ , p. 81–82 (ISSN 0031-9228 et 1945-0699, DOI 10.1063/1.1825279, lire en ligne, consulté le )
  9. Duncan J. Watts et Steven H. Strogatz, « Collective dynamics of ‘small-world’ networks », Nature, vol. 393, no 6684,‎ , p. 440–442 (ISSN 0028-0836 et 1476-4687, DOI 10.1038/30918, lire en ligne, consulté le )
  10. Erzsébet Ravasz et Albert-László Barabási, « Hierarchical organization in complex networks », Physical Review E, vol. 67, no 2,‎ (ISSN 1063-651X et 1095-3787, DOI 10.1103/physreve.67.026112, lire en ligne, consulté le )
  11. a et b E. Ravasz, « Hierarchical Organization of Modularity in Metabolic Networks », Science, vol. 297, no 5586,‎ , p. 1551–1555 (ISSN 0036-8075 et 1095-9203, DOI 10.1126/science.1073374, lire en ligne, consulté le )
  12. Rick Durrett, « Erdös–Rényi Random Graphs », dans Random Graph Dynamics, Cambridge University Press (ISBN 978-0-511-54659-4, lire en ligne), p. 27–69
  13. a b et c Albert-László Barabási et Zoltán N. Oltvai, « Network biology: understanding the cell's functional organization », Nature Reviews Genetics, vol. 5, no 2,‎ , p. 101–113 (ISSN 1471-0056 et 1471-0064, DOI 10.1038/nrg1272, lire en ligne, consulté le )
  14. a et b Albert-László Barabási et Réka Albert, « Emergence of Scaling in Random Networks », Science, vol. 286, no 5439,‎ , p. 509–512 (ISSN 0036-8075 et 1095-9203, DOI 10.1126/science.286.5439.509, lire en ligne, consulté le )
  15. Takuji Yamada et Peer Bork, « Evolution of biomolecular networks — lessons from metabolic and protein interactions », Nature Reviews Molecular Cell Biology, vol. 10, no 11,‎ , p. 791–803 (ISSN 1471-0072 et 1471-0080, DOI 10.1038/nrm2787, lire en ligne, consulté le )
  16. H. Jeong, S. P. Mason, A.-L. Barabási et Z. N. Oltvai, « Lethality and centrality in protein networks », Nature, vol. 411, no 6833,‎ , p. 41–42 (ISSN 0028-0836 et 1476-4687, DOI 10.1038/35075138, lire en ligne, consulté le )
  17. Andreas Wagner, « The Yeast Protein Interaction Network Evolves Rapidly and Contains Few Redundant Duplicate Genes », Molecular Biology and Evolution, vol. 18, no 7,‎ , p. 1283–1292 (ISSN 1537-1719 et 0737-4038, DOI 10.1093/oxfordjournals.molbev.a003913, lire en ligne, consulté le )
  18. Andreas Wagner, « How the global structure of protein interaction networks evolves », Proceedings of the Royal Society of London. Series B: Biological Sciences, vol. 270, no 1514,‎ , p. 457–466 (ISSN 0962-8452 et 1471-2954, DOI 10.1098/rspb.2002.2269, lire en ligne, consulté le )
  19. Eli Eisenberg et Erez Y. Levanon, « Preferential Attachment in the Protein Network Evolution », Physical Review Letters, vol. 91, no 13,‎ (ISSN 0031-9007 et 1079-7114, DOI 10.1103/physrevlett.91.138701, lire en ligne, consulté le )
  20. (en) Takuji Yamada et Peer Bork, « Evolution of biomolecular networks — lessons from metabolic and protein interactions », Nature Reviews Molecular Cell Biology, vol. 10, no 11,‎ , p. 791–803 (ISSN 1471-0072 et 1471-0080, DOI 10.1038/nrm2787, lire en ligne, consulté le )
  21. Alexei Vázquez, Alessandro Flammini, Amos Maritan et Alessandro Vespignani, « Modeling of Protein Interaction Networks », Complexus, vol. 1, no 1,‎ , p. 38–44 (ISSN 1424-8492 et 1424-8506, DOI 10.1159/000067642, lire en ligne, consulté le )
  22. Romualdo Pastor-Satorras, Eric Smith et Ricard V. Solé, « Evolving protein interaction networks through gene duplication », Journal of Theoretical Biology, vol. 222, no 2,‎ , p. 199–210 (ISSN 0022-5193, DOI 10.1016/s0022-5193(03)00028-6, lire en ligne, consulté le )
  23. R. Jansen, « A Bayesian Networks Approach for Predicting Protein-Protein Interactions from Genomic Data », Science, vol. 302, no 5644,‎ , p. 449–453 (ISSN 0036-8075 et 1095-9203, DOI 10.1126/science.1087361, lire en ligne, consulté le )
  24. Ziv Bar-Joseph, Georg K Gerber, Tong Ihn Lee et Nicola J Rinaldi, « Computational discovery of gene modules and regulatory networks », Nature Biotechnology, vol. 21, no 11,‎ , p. 1337–1342 (ISSN 1087-0156 et 1546-1696, DOI 10.1038/nbt890, lire en ligne, consulté le )
  25. Edward Butz, « Biochemical Systems Analysis. A Study of Function and Design in Molecular Biology (Michael A. Savageau) », SIAM Review, vol. 20, no 3,‎ , p. 613–615 (ISSN 0036-1445 et 1095-7200, DOI 10.1137/1020092, lire en ligne, consulté le )
  26. Gary D Bader et Christopher WV Hogue, « [No title found] », BMC Bioinformatics, vol. 4, no 1,‎ , p. 2 (PMID 12525261, PMCID PMC149346, DOI 10.1186/1471-2105-4-2, lire en ligne, consulté le )
  27. (en) Balázs Adamcsek, Gergely Palla, Illés J. Farkas et Imre Derényi, « CFinder: locating cliques and overlapping modules in biological networks », Bioinformatics, vol. 22, no 8,‎ , p. 1021–1023 (ISSN 1460-2059 et 1367-4803, DOI 10.1093/bioinformatics/btl039, lire en ligne, consulté le )
  28. (en) Gergely Palla, Imre Derényi, Illés Farkas et Tamás Vicsek, « Uncovering the overlapping community structure of complex networks in nature and society », Nature, vol. 435, no 7043,‎ , p. 814–818 (ISSN 0028-0836 et 1476-4687, DOI 10.1038/nature03607, lire en ligne, consulté le )
  29. Guimei Liu, Limsoon Wong et Hon Nian Chua, « Complex discovery from weighted PPI networks », Bioinformatics, vol. 25, no 15,‎ , p. 1891–1897 (ISSN 1460-2059 et 1367-4803, DOI 10.1093/bioinformatics/btp311, lire en ligne, consulté le )
  30. Etsuji Tomita, Akira Tanaka et Haruhisa Takahashi, « The worst-case time complexity for generating all maximal cliques and computational experiments », Theoretical Computer Science, vol. 363, no 1,‎ , p. 28–42 (ISSN 0304-3975, DOI 10.1016/j.tcs.2006.06.015, lire en ligne, consulté le )
  31. Coen Bron et Joep Kerbosch, « Algorithm 457: finding all cliques of an undirected graph », Communications of the ACM, vol. 16, no 9,‎ , p. 575–577 (ISSN 0001-0782 et 1557-7317, DOI 10.1145/362342.362367, lire en ligne, consulté le )
  32. Filippo Geraci, Maurizio Martinelli, Marco Pellegrini et Michela Serrecchia, « A Framework to Evaluate Information Quality in Public Administration Website », Pacific Asia Journal of the Association for Information Systems,‎ , p. 25–42 (ISSN 1943-7544, DOI 10.17705/1pais.05302, lire en ligne, consulté le )
  33. a b et c Oleksii Kuchaiev, Tijana Milenković, Vesna Memišević et Wayne Hayes, « Topological network alignment uncovers biological function and phylogeny », Journal of the Royal Society Interface, vol. 7, no 50,‎ , p. 1341–1354 (ISSN 1742-5689, PMID 20236959, PMCID 2894889, DOI 10.1098/rsif.2010.0063, lire en ligne, consulté le )
  34. a b et c (en) Rob Patro et Carl Kingsford, « Global network alignment using multiscale spectral signatures », Bioinformatics, vol. 28, no 23,‎ , p. 3105–3114 (ISSN 1367-4803, DOI 10.1093/bioinformatics/bts592, lire en ligne, consulté le )
  35. (en) Vikram Saraph et Tijana Milenković, « MAGNA: Maximizing Accuracy in Global Network Alignment », Bioinformatics, vol. 30, no 20,‎ , p. 2931–2940 (ISSN 1367-4803, DOI 10.1093/bioinformatics/btu409, lire en ligne, consulté le )
  36. (en) Sayed Mohammad Ebrahim Sahraeian et Byung-Jun Yoon, « RESQUE: Network reduction using semi-Markov random walk scores for efficient querying of biological networks », Bioinformatics, vol. 28, no 16,‎ , p. 2129–2136 (ISSN 1367-4803, DOI 10.1093/bioinformatics/bts341, lire en ligne, consulté le )
  37. Debnath Pal, « On gene ontology and function annotation », Bioinformation, vol. 1, no 3,‎ , p. 97–98 (ISSN 0973-2063, PMID 17597866, PMCID 1891657, lire en ligne, consulté le )
  38. (en) Oleksii Kuchaiev et Nataša Pržulj, « Integrative network alignment reveals large regions of global network similarity in yeast and human », Bioinformatics, vol. 27, no 10,‎ , p. 1390–1396 (ISSN 1367-4803, DOI 10.1093/bioinformatics/btr127, lire en ligne, consulté le )
  39. (en) Behnam Neyshabur, Ahmadreza Khadem, Somaye Hashemifar et Seyed Shahriar Arab, « NETAL: a new graph-based method for global alignment of protein–protein interaction networks », Bioinformatics, vol. 29, no 13,‎ , p. 1654–1662 (ISSN 1367-4803, DOI 10.1093/bioinformatics/btt202, lire en ligne, consulté le )
  40. Philip Resnik, « Using Information Content to Evaluate Semantic Similarity in a Taxonomy », arXiv:cmp-lg/9511007,‎ (lire en ligne, consulté le )
  41. (en) Ahmet E. Aladağ et Cesim Erten, « SPINAL: scalable protein interaction network alignment », Bioinformatics, vol. 29, no 7,‎ , p. 917–924 (ISSN 1367-4803, DOI 10.1093/bioinformatics/btt071, lire en ligne, consulté le )
  42. A. Elmsallati, A. Msalati et J. Kalita, « Index-Based Network Aligner of Protein-Protein Interaction Networks », IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol. 15, no 1,‎ , p. 330–336 (ISSN 1557-9964, DOI 10.1109/TCBB.2016.2613098, lire en ligne, consulté le )
  43. (en) V. Vijayan, V. Saraph et T. Milenković, « MAGNA++: Maximizing Accuracy in Global Network Alignment via both node and edge conservation », Bioinformatics, vol. 31, no 14,‎ , p. 2409–2411 (ISSN 1367-4803, DOI 10.1093/bioinformatics/btv161, lire en ligne, consulté le )
  44. a b c et d Sarra Ghanjeti, « Alignment of Protein-Protein Interaction Networks », arXiv:1911.09959 [q-bio],‎ (lire en ligne, consulté le )
  45. (en) Roman L. Tatusov, Eugene V. Koonin et David J. Lipman, « A Genomic Perspective on Protein Families », Science, vol. 278, no 5338,‎ , p. 631–637 (ISSN 0036-8075 et 1095-9203, PMID 9381173, DOI 10.1126/science.278.5338.631, lire en ligne, consulté le )
  46. a et b D. Park, R. Singh, M. Baym et C.-S. Liao, « IsoBase: a database of functionally related proteins across PPI networks », Nucleic Acids Research, vol. 39, no Database,‎ , D295–D300 (ISSN 0305-1048 et 1362-4962, DOI 10.1093/nar/gkq1234, lire en ligne, consulté le )